#include "main/utils.h"
using namespace std;

class RandomMap {
  public:
    bool insert(int value) {
      if (map.find(value) == map.end()) {
        int count = vec.size();
        map.insert(make_pair(value, count));
        vec.push_back(value);
        return true;
      }
      return false;
    }

    bool remove(int value) {
      if (map.find(value) != map.end()) {
        int idx = map[value];
        int tail_idx = vec.size() - 1;
        map[vec[tail_idx]] = idx;
        map.erase(value);
        vec[idx] = vec[tail_idx];
        vec.erase(vec.end() - 1);
        return true;
      }
      return false;
    }
    
    int getRandom() {
      int count = vec.size();
      int random_idx = rand() % count;
      return vec[random_idx];
    }

  public:
    vector<int> vec;
    map<int, int> map;
};

int main() {
  RandomMap map;
  cout << map.insert(1) << endl;
  printVec("insert 1", map.vec);
  cout << map.insert(2) << endl;
  printVec("insert 2", map.vec);
  cout << map.insert(3) << endl;
  printVec("insert 3", map.vec);
  cout << map.insert(2) << endl;
  printVec("insert 2", map.vec);
  cout << map.getRandom() << endl;
  printVec("getRandom", map.vec);
  cout << map.remove(1) << endl;
  printVec("remove 1", map.vec);
  cout << map.remove(2) << endl;
  printVec("remove 2", map.vec);
  cout << map.remove(2) << endl;
  printVec("remove 2", map.vec);

  return 0;
}
